// https://www.lintcode.com/problem/binary-search-tree-iterator/my-submissions
// 86. 二叉查找树迭代器
// 设计实现一个带有下列属性的二叉查找树的迭代器：
// next()返回BST中下一个最小的元素

// 元素按照递增的顺序被访问（比如中序遍历）
// next()和hasNext()的询问操作要求均摊时间复杂度是O(1)
// 样例
// 对于下列二叉查找树，使用迭代器进行中序遍历的结果为 [1, 6, 10, 11, 12]

//   10
//  /    \
// 1      11
//  \       \
//   6       12
// 挑战
// 额外空间复杂度是O(h)，其中h是这棵树的高度

// Super Star：使用O(1)的额外空间复杂度


/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 * Example of iterate a tree:
 * BSTIterator iterator = BSTIterator(root);
 * while (iterator.hasNext()) {
 *    TreeNode * node = iterator.next();
 *    do something for node
 */


// class BSTIterator {
// public:
//     /*
//     * @param root: The root of binary tree.
//     */
//     vector<TreeNode*> traverse_list;
//     BSTIterator(TreeNode * root) {
//         traverse(root);
//     }

//     /*
//      * @return: True if there has next node, or false
//      */
//     bool hasNext() {
//         return !traverse_list.empty();
//     }

//     /*
//      * @return: return next node
//      */
//     TreeNode * next() {
//         TreeNode* tmp = traverse_list.back();
//         traverse_list.pop_back();
//         return tmp;
//     }
    
//     void traverse(TreeNode * root)
//     {
//         if (!root)
//         {
//             return;
//         }
//         traverse(root->left);
//         traverse_list.insert(traverse_list.begin(), root);
//         traverse(root->right);
//     }
// };


// stack,遍历的过程就在next()的过程中(其实就是最外层的while(!s.empty())转化hasNext()，然后反复调用next()函数)
// class BSTIterator {
// public:
//     /*
//     * @param root: The root of binary tree.
//     */
//     stack<TreeNode*> s;
//     TreeNode * cur;
//     BSTIterator(TreeNode * root) {
//         cur = root;
//     }

//     /*
//      * @return: True if there has next node, or false
//      */
//     bool hasNext() {
//         return cur || !s.empty(); //最外层while的判断
//     }

//     /*
//      * @return: return next node
//      */
//     TreeNode * next() {
//         while (cur)
//         {
//             s.push(cur);
//             cur = cur->left;
//         }
//         TreeNode * tmp = s.top();
//         s.pop();
//         cur = tmp->right;
//         return tmp;
//     }
// };



class BSTIterator {
public:
    /*
    * @param root: The root of binary tree.
    */
    TreeNode * pre;
    TreeNode * cur;
    BSTIterator(TreeNode * root) {
        pre = NULL;
        cur = root;
    }

    /*
     * @return: True if there has next node, or false
     */
    bool hasNext() {
        return cur!=NULL; //最外层while的判断
    }

    /*
     * @return: return next node
     */
    TreeNode * next() {
        while (cur)
        {
            s.push(cur);
            cur = cur->left;
        }
        TreeNode * tmp = s.top();
        s.pop();
        cur = tmp->right;
        return tmp;
    }
};